package com.lun.swordtowardoffer2.c15;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class IsBipartite {

	public boolean isBipartite(int[][] graph, SetColor sc) {
		int size = graph.length;
		int[] colors = new int[size];
		
		Arrays.fill(colors, -1);
		
		for(int i = 0; i < size; i++) {
			if(colors[i] == -1 && !sc.setColor(graph, colors, i, 0)) {
				return false;
			}
		}
		
		return true;
	}
	
	public abstract class SetColor{
		public abstract boolean setColor(int[][] graph, int[] colors, int i, int color);
	}
	
	public class SetColorByBFS extends SetColor{

		@Override
		public boolean setColor(int[][] graph, int[] colors, int i, int color) {
			Queue<Integer> queue = new LinkedList<>();
			queue.offer(i);
			colors[i] = color;
			while (!queue.isEmpty()){
				int cur = queue.poll();
				for(int neighbor : graph[cur]) {
					if(colors[neighbor] >= 0) {
						if(colors[neighbor] == colors[cur]) {
							return false;
						}	
					}else {
						colors[neighbor] = 1 - colors[cur];
						queue.offer(neighbor);
					}
				}
			}
			
			return true;
		}
		
	}
	
	public class SetColorByDFS extends SetColor{

		@Override
		public boolean setColor(int[][] graph, int[] colors, int i, int color) {
			if(colors[i] >= 0) {
				return colors[i] == color;
			}
			colors[i] = color;
			
			for(int neighbor : graph[i]) {
				if(!setColor(graph, colors, neighbor, 1 - color)) {
					return false;
				}
			}
			
			return true;
		}
		
	}
	
}
